package _线性;

import com.sun.org.glassfish.external.amx.AMX;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;

public class _xx {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap1(arr, j, j + 1);
                    flag = true;
                }
            }
            if (!flag)
                break;
        }
    }

    private static void swap1(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void insertSort1(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            //选择合适的元素把它插入到已排序的位置
            int key = arr[i];
            int j = i - 1;
            // 从后向前移动，空一个位置给
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void selectionSort1(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min])
                    min = j;
            }
            if (min != i)
                swap1(arr, min, i);
        }
    }

    // 快速排序算法
    // 选择一个基准元素，将其放到数组中的合适位置，使其左边都小于它
    public static void quickSort1(int[] arr, int l, int r) {
        // 递归终止条件
        if (l < r) {
            int pi = patitation(arr, l, r);
            quickSort1(arr, l, pi - 1);
            quickSort1(arr, pi + 1, r);

        }

    }

    // 7 2 1 6 5 （i = 0）
    // 2 7 1 6 5 （i = 1）
    // 2 1 7 6 5 （i = 2）
    // 2 1 5 6 7  return 2
    private static int patitation(int[] arr, int l, int r) {
        int key = arr[r];
        int i = l;
        for (int j = l; j < r; j++) {
            if (arr[j] < key)
                swap1(arr, i++, j);
        }
        swap1(arr, i, r);
        return i;
    }

    // 堆排序算法
    // 当前节点的孩子节点的位置
    public static void heapSort1(int[] arr) {
        int n = arr.length;
        for (int i = n / 2; i >= 0; i--) {
            maxHeapy(arr, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            swap1(arr, 0, i);

            maxHeapy(arr, i, 0);
        }
    }

    /**
     * @param arr
     * @param n   当前堆的有效大小
     * @param i   需要堆化的节点索引
     */
    private static void maxHeapy(int[] arr, int n, int i) {
        // 操作索引不直接操作元素
        int max = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < n && arr[l] > arr[max]) {
            max = l;
        }
        if (r < n && arr[r] > arr[max]) {
            max = r;
        }
        if (max != i) {
            swap1(arr, i, max);
            maxHeapy(arr, n, max);
        }
    }

    // 347：100题 前 k 个高频元素：https://leetcode.cn/problems/top-k-frequent-elements/
    public int[] topKFrequent(int[] nums, int k) {
        // 用于存储每个元素的频率
        HashMap<Integer, Integer> map = new HashMap<>();

        // 存到优先级队列里
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        pq.addAll(map.entrySet());

        // 取出 k 个频率最高的元素
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = pq.poll().getKey();
        }
        return ans;
    }
}
